1. Field of the Invention
The present invention relates generally to memory devices, and more particularly to content addressable memory devices searchable using words spanning multiple rows in memory.
2. Description of the Related Art
Memory devices are indispensable components of modem computer systems and networks. As storage devices, they are used to provide fast access to data and instructions stored therein. A content addressable memory (CAM) is a special type of memory that is often used for performing address searches. For example, Internet routers often include a CAM for searching the address of specified data. The use of CAMs allows the routers to perform fast searches to allow computer systems to communicate data with one another over networks. In addition, CAMs are utilized in numerous other areas such as database searches, image processing, and voice recognition applications, where fast search performance is desired.
As is well known, CAMs typically include a two-dimensional row and column content address memory array of core cells, such that each row contains an address, pointer, or bit pattern entry. Within such an array of cells, a CAM may perform “read “and ”write” operations at specific addresses like a conventional random access memory (RAM). In addition, a CAM is used to perform fast search operations that simultaneously compare a bit pattern of data, known as a comparand, against an entire list (e.g., column) of pre-stored entries (e.g., rows) of bit patterns in the CAM array. Based on these comparisons, the CAM typically outputs a result in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data. By thus performing comparisons simultaneously of all CAM entries, the CAM provides significant savings in search time over RAMs such as DRAMs, SRAMs, and the like.
A CAM typically can perform high-speed searches on comparands or search keys of a particular bit length, known as the word width. However, available word widths in conventional CAMs arc limited by the physical organization of the CAM. FIG. 1 is a logical diagram showing a conventional CAM array 100. The CAM array 100 comprises a plurality of bit pattern entries 102, each comprising a plurality of CAM cells 104 coupled to a match line 106. In use, each CAM cell 104 stores a bit of the bit pattern entry 102, while the match line 106 is used to indicate the match results of search operations.
During a search operation, a comparand is compared against each bit pattern entry 102 in the CAM array 100 by comparing the individual bits of the comparand against the corresponding CAM cell 104 of the bit pattern entry 102. If each CAM cell 104 of the bit pattern entry 102 matches the corresponding bit of the comparand, the match line 106 of the bit pattern entry is high. However, CAM cells 104 that do not match the comparand ground the match line 106, thus pulling the match line 106 for the bit pattern entry 102 low when the comparand does not match the data stored in the bit pattern entry 102.
As can be seen from FIG. 1, the word width usable in a conventional CAM is limited by the actual physical dimensions of the CAM array 100. In particular, a conventional CAM requires each word, or bit pattern entry 102, to be organized such that the entire word occupies a row of the CAM array 100 along a match line 106. Unfortunately, this physical restriction limits the word width available when using conventional CAMs.
More particularly, a CAM chip must fit within a package, which implies physical limitations on the actual dimensions of the CAM memory. Generally, CAM memories can only be built to a particular size before 1) performance degrades and 2) the chip no longer fits within the packaging. Performance degradation often results from extra loading caused from using long match lines, which are conventionally needed when using extended word widths.
In view of the foregoing, there is a need for CAM architectures wherein the word width is not limited by the physical width of the CAM memory. In particular, the CAM architectures should allow for word width sizes greater than the width of a single CAM row, thereby maximizing the usage of CAM space with attendant savings in cost.